package com.lhcai.lc.category.dynamicprogramming;

import java.util.Arrays;

/**
 * 53. 最大子数组和
 * 前缀和和法： 求出前缀和-最小前缀和，再更新最小前缀和
 * Dynamic Programming
 *
 * @author liuhuaicai
 * @since 2024-10-27 11:09
 */
public class Lc53 {
    public static void main(String[] args) {
        Lc53 lc53 = new Lc53();
        System.out.println(lc53.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

    /**
     * dp[i] = dp[i-1]  + nums[i];
     *
     * @param nums 整数数组
     * @return 连续子数组的的最大和
     */
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}
